/* Copyright (C) 2020 G'k
 * Imported by Holt59
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
#ifndef GLOB_MATCHING_H
#define GLOB_MATCHING_H

#include <cctype>
#include <string_view>
#include <QString>

namespace MOShared {

  /**
   * Contraints string_traits to allow usage of both standard strings and QString in
   * GlobPattern.
   */
  namespace details {

    template <
      class CharT,
      class Traits = std::char_traits<CharT>,
      class Allocator = std::allocator<CharT>>
    struct string_traits {
      using string_type = std::basic_string<CharT, Traits, Allocator>;
      using string_view = std::basic_string_view<CharT, Traits>;

      static auto tolower(CharT c) { return std::tolower(c); }

      static auto empty(string_view const& view) { return view.empty(); }
    };

    template <>
    struct string_traits<QChar> {
      using string_type = QString;
      using string_view = QString;

      static auto tolower(QChar const& c) { return c.toLower(); }
      static auto empty(string_view const& view) { return view.isEmpty(); }
    };

  }

  /**
   * @brief Class that provides basic wildcard pattern matching.
   *
   * From https://gitlab.com/G_ka/playground/-/commits/master/include/wildcards.hpp
   *
   * Currently, this supports the following globbing character:
   *  - '*' matches zero or more characters.
   *  - '?' matches exactly one character.
   *  - '[abc]' matches one of 'a', 'b' or 'c'.
   *
   * Standard globbing feature not supported:
   *  - You cannot escape globbing characters with \.
   *  - You cannot use `[a-z]` to match any character from 'a' to 'z'.
   *
   * Custom class because the following alternatives have some issues:
   *  - QRegExp is a tad slow, and we need to convert everything to QString.
   *  - QDir::match is VERY slow. I think it converts the glob pattern to a QRegularExpression and
   *    then use it.
   *  - PatchMatchSpecW (Windows API) is fast but does not support some useful glob pattern (e.g., 
   *    [ab]).
   *
   * Advantage of this over the above methods:
   *  - It is fast. Quick testing show that this is faster than PatchMatchSpecW.
   *  - It can be used on most string types (QString, std::string, std::wstring, etc.).
   */
  template <
    class CharT,
    class Traits = std::char_traits<CharT>,
    class Allocator = std::allocator<CharT>>
    class GlobPattern {
    public:

      using traits = details::string_traits<CharT, Traits, Allocator>;

      using string_type = typename traits::string_type;
      using string_view_type = typename traits::string_view;

      struct card {
        // Relying on automatic conversion:
        static constexpr CharT any = '?';
        static constexpr CharT any_repeat = '*';
        static constexpr CharT set_begin = '[';
        static constexpr CharT set_end = ']';
      };

    public:

      GlobPattern(string_view_type const& s) : v{ s } { }

      const string_type& native() const { return v; }

      constexpr bool match(
        string_view_type const& str,
        bool case_sensitive = false)
      {
        // Empty pattern can only match with empty sting
        if (traits::empty(v))
          return traits::empty(str);

        auto pat_it = v.begin();
        auto pat_end = v.end();

        auto str_it = str.begin();
        auto str_end = str.end();

        auto anyrep_pos_pat = pat_end;
        auto anyrep_pos_str = str_end;

        auto set_pos_pat = pat_end;

        while (str_it != str_end)
        {
          CharT current_pat = 0;
          CharT current_str = -1;
          if (pat_it != pat_end)
          {
            current_pat = case_sensitive ? *pat_it : traits::tolower(*pat_it);
            current_str = case_sensitive ? *str_it : traits::tolower(*str_it);
          }
          if (pat_it != pat_end && current_pat == card::set_begin)
          {
            set_pos_pat = pat_it;
            pat_it++;
          }
          else if (pat_it != pat_end && current_pat == card::set_end)
          {
            if (anyrep_pos_pat != pat_end)
            {
              set_pos_pat = pat_end;
              pat_it++;
            }
            else
            {
              return false;
            }

          }
          else if (set_pos_pat != pat_end)
          {
            if (current_pat == current_str)
            {
              set_pos_pat = pat_end;
              pat_it = std::find(pat_it, pat_end, card::set_end) + 1;
              str_it++;
            }
            else
            {
              if (pat_it == pat_end)
              {
                return false;
              }
              pat_it++;
            }
          }
          else if (pat_it != pat_end && current_pat == current_str)
          {
            pat_it++;
            str_it++;
          }
          else if (pat_it != pat_end && current_pat == card::any)
          {
            pat_it++;
            str_it++;
          }
          else if (pat_it != pat_end && current_pat == card::any_repeat)
          {
            anyrep_pos_pat = pat_it;
            anyrep_pos_str = str_it;
            pat_it++;
          }
          else if (anyrep_pos_pat != pat_end)
          {
            pat_it = anyrep_pos_pat + 1;
            str_it = anyrep_pos_str + 1;
            anyrep_pos_str++;
          }
          else
          {
            return false;
          }
        }
        while (pat_it != pat_end)
        {
          CharT cur = case_sensitive ? *pat_it : traits::tolower(*pat_it);
          if (cur == card::any_repeat)
            pat_it++;
          else
            break;
        }
        return pat_it == pat_end;
      }

    private:
      string_type v;
  };

  template <class CharT, class Traits, class Allocator>
  GlobPattern(std::basic_string<CharT, Traits, Allocator> const&)
    -> GlobPattern<CharT, Traits, Allocator>;

  template <class CharT>
  GlobPattern(CharT const*) -> GlobPattern<CharT>;

  GlobPattern(QString const&) -> GlobPattern<QChar>;


} // namespace wildcards

#endif
